package divide;

/**
 * @Description 50. Pow(x, n)
 * @Author Firenut
 * @Date 2023-03-26 18:09
 */
public class T50_myPow {
    /**
     * 思路:
     * (x)^n == (x^2)^(n/2) <==> (x^b)^1
     * 直到指数为1时,return x^b; x^b是一个整体,每一次指数/2的时候都被计算进来
     * 可以从分治的角度，也可以从二进制的角度去理解;个人感觉分治角度好理解一点
     */

    // 从分治角度
    public double myPow(double x, int n) {
        long b = n;     // 如果n==Math.MIN_VALUE,则-n会溢出,所以先转long存储
        if (b < 0) {    // 指数<0的处理
            x = 1 / x;
            b = -b;
        }
        double y = 1;
        while (b > 0) {
            if ((b & 1) == 1) {  // 如果为1说明是奇数(也就是说二进制的末位决定该数是奇数还是偶数，如果为1则为奇数，如果为0则为偶数)
                y *= x; // 如果为奇数,则指数/2之后会漏掉一个x,需要补上
            }
            x *= x;  // 每次执行x^2
            b >>= 1; // 指数做除2操作
        }
        return y;
    }


    /**
     * 从二进制角度
     * eg: x^3 <==> x^(011) <==> x^(1 * 2^0 + 1 * 2^1 + 0 * 2^2)
     * <==> x^(1 * 2^0) * x^(1 * 2^1) *  x^(0 * 2^2) <==> x^(1*(1)) * x^(2*(1)) *  x^(4*(0))
     */
    public double myPow1(double x, int n) {
        long b = n;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        double y = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                y *= x; // 二进制位对应的数为1时,才有 y *= x; 不然该值为(2^(b*0))==1,就没必要乘进去了
            }
            x *= x;  // 每次执行x^2 (x * x^2 * x^4 * x^8 ...)
            b >>= 1; // 右移,依次判断二进制每一位
        }
        return y;
    }
}